package com.study.algorithm.base.list;

import com.google.common.collect.Lists;
import com.study.algorithm.base.common.ListUtil;

import java.util.List;

/**
 * InsertSort
 *
 * 时间复杂度 O(N^2) , 额外空间复杂度O(1)
 *
 * 受数据状况
 *
 * @author wanghuilong
 * @version 1.0
 * @description insert sort
 * @date 2022/11/6 16:18
 */
public class InsertSort {


    public static void main(String[] args) {
        List<Integer> list = ListUtil.getRandomList(10);
//        list = Lists.newArrayList(1,2,3,4,5,6,7,8);
        System.out.println(list);
        insertSort(list);
    }

    public static void insertSort(List<Integer> list) {
        //0~0范围上有序
        //0~1范围上有序
        //......
        //0~len-1范围上有序
        for (int i = 1; i < list.size(); i++) {  // 0~ i做到有序

            for (int j = i ; j > 0; j--) {
                if(list.get(j) < list.get(j-1)) {
                    ListUtil.swap(list,j,(j-1));
                }
            }
        }
        System.out.println(list);
    }

}
